package com.myown.algorithm;

import java.util.ArrayList;
import java.util.List;

/**
 * 动态规划 <p>
 *
 * 动态规划思路：
 * 1. 将原问题分解为子问题
 * 2.确定状态s
 * 3.确定一些初始状态（边界状态）的值
 * 4. 确定状态转移方程 <p>
 *
 * @author lincky
 * @version v1.0.0
 * @time 2017/3/26 22:16
 */

public class DP {

    public int find(int line) {
        Triangle triangle = new Triangle(line);
        return triangle.find();
    }

    /**
     * 数字三角形中寻找一条从顶部到底边的路径，使得路
     * 径上所经过的数字之和最大
     */
    class Triangle {
        int line;
        int[][] items;
        int[][] max;

        public Triangle(int line) {
            items = new int [line][line];
            max = new int [line][line];
            this.line = line;
            triangulate(line);
        }

        private void triangulate(int line) {
            for (int i = 0; i < line; i++) {
                for (int j = 0; j <= i; j++) {
                    items[i][j] = random();
                    max[i][j] = -1;
                }
            }
        }

        public int find() {
            print();
            for (int i = 0; i < line; i++) {
                max[line - 1][i] = items[line - 1][i];
            }
            for (int i = line - 2; i >= 0; i--) {
                for (int j = 0; j <= i ; j++) {
                    max[i][j] = Math.max(max[i + 1][j], max[i + 1][j + 1]) +
                            items[i][j];
                }
            }
            return max[0][0];
        }

        private void print() {
            for (int i = 0; i < line; i++) {
                for (int j = 0; j <= i; j++) {
                    System.out.print(items[i][j] + " ");
                }
                System.out.println();
            }
        }

        private int random() {
            return RandomUtil.getRandom(9);
        }

    }

    /**
     * 查找最长公共子串(二维数组改进版) <p>
     *
     * &nbsp&nbsp b   a   b <p>
     * c    0   0   0 <p>
     *
     * a    0   1   1 <p>
     *  &nbsp&nbsp&nbsp&nbsp&nbsp&nbsp \   <p>
     * b    1   1   2 <p>
     *
     * a    0   1   1 <p>
     *
     * 步骤：
     * 1.记录对角线匹配次数：遍历
     * 2.大于当前最大子串长度：消除记录
     * 3.多个相同子串：记录
     *
     * @param a 字符串
     * @param b 字符串
     * @return 最长公约子字符串
     */
    public List<String> longgestCommonSubstring(String a, String b) {
        int maxLen = a.length() > b.length() ? a.length() : b.length();
        // 匹配索引
        int[] index = new int [maxLen];
        // 匹配长度
        int[] max = new int [maxLen];
        // 对角线匹配次数
        int[] diagonal = new int [maxLen];
        for (int i = 0; i < a.length(); i++) {
            for (int j = b.length() - 1; j >= 0; j--) {
                // 记录对角线匹配次数
                if (a.charAt(i) == b.charAt(j)) {
                    if (i == 0 || j == 0) {
                        diagonal[j] = 1;
                    } else {
                        diagonal[j] = diagonal[j - 1] + 1;
                    }
                } else {
                    diagonal[j] = 0;
                }
                // 大于当前最大子串长度
                if (diagonal[j] > max[0]) {
                    max[0] = diagonal[j];
                    index[0] = j;
                    for (int k = 1; k < maxLen; k++) {
                        max[k] = 0;
                        index[k] = 0;
                    }
                }
                // 多个相同子串
                else if (diagonal[j] == max[0]) {
                    for (int k = 1; k < maxLen; k++) {
                        if (max[k] == 0) {
                            max[k] = diagonal[j];
                            index[k] = j;
                            break;
                        }
                    }
                }
            }
        }
        List<String> list = new ArrayList<>();
        for (int i = 0; i < maxLen; i++) {
            if (max[i] > 0) {
                list.add(b.substring(index[i] - max[i] + 1, index[i] + 1));
            }
        }
        return list;
    }

    public int continuityMax(int[] data,
                             int low,
                             int high) {
        int max = 0,sum = 0;
        int sumStart, sumEnd;
        for (int i = low; i < high; i++) {
            if (sum > 0) {
                sum += data[i];
                sumEnd = i;
            } else {
                sum = data[i];
                sumStart = i;
                sumEnd = i;
            }
            if (sum > max) {
                max = sum;

            }
        }
        return max;
    }

}
